package com.yt.ds.chapter4;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author: lzf
 * @Date: 2020/7/31 09:47
 * @Description: 有向图中基于深度优先搜索的顶点排序
 */
public class DepthFirstOrder {
    private boolean[] marked;
    private Queue<Integer> pre;         // 前序
    private Queue<Integer> post;        // 后序
    private Stack<Integer> reversePost; // 逆后序

    public DepthFirstOrder(Graph graph) {
        pre = new LinkedList<>();
        post = new LinkedList<>();
        reversePost = new Stack<>();
        marked = new boolean[graph.getVertexNum()];

        for (int v = 0; v < graph.getVertexNum(); v++) {
            if (!marked[v]) {
                dfs(graph, v);
            }
        }
    }

    private void dfs(Graph graph, int v) {
        pre.offer(v);

        marked[v] = true;
        for(int w : graph.adj(v)){
            if(!marked[w]){
                dfs(graph,w);
            }
        }

        post.offer(v);
        reversePost.push(v);
    }

    public Iterable<Integer> pre() {
        return pre;
    }

    public Iterable<Integer> post() {
        return post;
    }

    public Iterable<Integer> reversePost() {
        return reversePost;
    }
}
